計數是透過邏輯結構來判斷有限集合大小的藝術,無需費力地逐一清點。藉由這種方法,我們可以解決從簡單的菜單組合到複雜的密碼學排列等各種問題。
"或"與"且"的邏輯
兩個核心原則支撐著整個組合數學領域。其應用完全取決於我們是否將任務視為從多個類別中做單一選擇,還是作為一系列連續的選擇。
加法原理(求和規則)
若集合 $X$ 被劃分為互不重疊的子集 $X_1, X_2, \dots, X_n$,則總元素數 $|X|$ 等於這些子集大小的總和:
$$|X| = |X_1| + |X_2| + \dots + |X_n|$$
類比: 在凱的速食餐廳點餐時,你可以從主菜選一份三明治,或從開胃菜選一種,但不能兩者都選;你只能挑選其中一個項目。
乘法原理(乘積規則)
若某項活動包含 $t$ 個連續步驟,其中第 $i$ 步有 $n_i$ 種可能結果,則完成該任務的總方式數等於各步可能性的乘積:
$$N = n_1 \times n_2 \times \dots \times n_t$$
類比: 設定一輛「大貨車」的配置。你必須選擇一台引擎(5種選項)與一種駕駛室款式(3種選項)。總共的組合數為 $5 \times 3 = 15$ 種。
程式實作與複雜度
在電腦科學中,這些原理體現在迴圈結構上。順序執行的迴圈代表加法原理,而巢狀迴圈則代表乘法原理。
// 加法原理(執行次數:m + n)
for i = 1 到 m:println(i)
for j = 1 到 n:println(j)
// 乘法原理(執行次數:m × n)
for i = 1 到 m:
for j = 1 到 n:
println(i, j)
for i = 1 到 m:println(i)
for j = 1 到 n:println(j)
// 乘法原理(執行次數:m × n)
for i = 1 到 m:
for j = 1 到 n:
println(i, j)
🎯 核心原則
根據關鍵字區分:"或"代表加法(互斥的選擇),而"且"或"連續"則代表乘法(序列中的獨立步驟)。